public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}
class Solution {
    public int[] productExceptSelf(int[] nums) {
        //构造前缀积数组
        int[] fdp = new int[nums.length];
        for (int i = 0;i < nums.length;i++) {
            if (i == 0) fdp[i] = 1;
            else fdp[i] = fdp[i-1]*nums[i-1];
        }
        //构造后缀积数组
        int[] bdp = new int[nums.length];
        for (int i = nums.length-1;i >= 0;i--) {
            if (i == nums.length-1) bdp[i] = 1;
            else bdp[i] = bdp[i+1]*nums[i+1];
        }
        //使用两个数组
        int[] ret = new int[nums.length];
        for (int i = 0;i < nums.length;i++) {
            ret[i] = fdp[i]*bdp[i];
        }
        return ret;
    }
}